#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10

typedef int ElemType;
// typedef struct SqList01
// {
//     ElemType pList[MAXSIZE];
//     int length;
// }SqList01; //顺序表的静态结构 

//顺序表的动态结构
typedef struct SqList
{
    ElemType *pList;//malloc
    int length;
    int listSize;
}SqList;

//给动态的顺序表进行初始化
void initSqlist(SqList *L){
    L->pList = (ElemType *)malloc(sizeof(ElemType)*MAXSIZE);
    L->length = 0;
    L->listSize = MAXSIZE;
}
//打印顺序表的信息
void print(SqList *L){
    printf("the length is %d , the listSize is %d \n",L->length,L->listSize);
    for (int i = 0; i < L->length; i++)
    {
      printf(" %d ",L->pList[i]) ; 
    }
    printf("\n");
}
//在第i个元素前插入e
int insert(SqList *L,int ith,ElemType e ){
    //判断i是否合法
    if(ith < 1 || ith > L->length){
        return 0;
    }
    //判断是否有容量插入，没有就扩容
    if(L->length  >= L->listSize){
            //扩容
        ElemType * pNew = (ElemType *)malloc(sizeof(ElemType)*MAXSIZE*2);
        for (int i = 0; i < L->length; i++)
        {   //复制到新空间
            pNew[i] = L->pList[i];
        }
        L->pList = pNew;
        L->listSize = MAXSIZE*2;
    }
    //让i及i之后的所有元素后移一位，然后插入
    for (int i = L->length-1; i >= ith - 1; i--)
    {
       L->pList[i+1] =  L->pList[i];
    }
    L->pList[ith-1] = e;
    L->length++;
    return 1;
    
}
//删除第i个元素
int delete(SqList *L,int ith){
    //判断i是否合法
    if(ith < 1 || ith > L->length){
        return 0;
    }
    for (int i = ith -1; i < L->length-1; i++)
    {
       L->pList[i] =  L->pList[i+1];
    }
    L->length--;
    return 1;
}
//删除最小元素，用最后一个元素填补
int deleteMin(SqList *L){
    int minIndex = 0;
    for (int i = 1; i < L->length; i++)
    {
        if(L->pList[i] < L->pList[minIndex]){
            minIndex = i;
        }
    }
    L->pList[minIndex] = L->pList[L->length-1];
    L->length--;
    return 1;
}
//删除无序表的s-t范围的元素
/**
 * 过滤法
 * 使用条件：结果子序列 <=当前访问过的序列长度
 */
void deleteElems(SqList *L,int s, int t){
    int curLength = 0; //结果子序列的长度
    for (int i = 0; i < L->length; i++)
    {
        if(L->pList[i]<s || L->pList[i] >t){
            L->pList[curLength++] =  L->pList[i];
        }
    }
    L->length = curLength;
    
}
//非递增删除 s-t 
void deleteA(SqList*L,int s, int t){
    int start = 0;
    int last = L->length-1;
    for (int i = 0; i < L->length; i++)
    {
       if(L->pList[i]>=s && L->pList[i] <=t){
        start = i;
        break;
       }
    }
    for (int i =L->length-1 ; i >= 0; i--)
    {
       if(L->pList[i]>=s && L->pList[i] <=t){
        last = i;
        break;
       }
    }
    int k = last -start +1; //后边元素偏移的距离
    for (int i = last +1; i < L->length; i++)
    {
       L->pList[i-k] = L->pList[i];
    }
    L->length -= k;

    
}
//删除重复元素，有序顺序表
int deleteSame(SqList *L){
    int curLength = 1;
    for (int  i = 1; i < L->length; i++)
    {
        if(L->pList[i] != L->pList[curLength-1]){
            L->pList[curLength++] = L->pList[i] ;
        }
    }
    L->length = curLength;
    
}
//合并两个表为第三个表
int combine(SqList *La,SqList*Lb,SqList*Lc){
    int i = 0,j = Lb->length-1;
    int curLength = 0;
    while (i <La->length && j>=0)
    {
        if(La->pList[i] > Lb->pList[j]){
                Lc->pList[curLength++] = Lb->pList[j--];
        }else{
            //A表元素值小于等于B表，如果等于优先插入A表
            Lc->pList[curLength++] = La->pList[i++];
        }
    }

    while (i <La->length)
    {
        Lc->pList[curLength++] = La->pList[i++];
    }

     while (j>=0)
    {
        Lc->pList[curLength++] = Lb->pList[j--];
    }
    Lc->length = curLength;
    return 1;
}
//最大值法合并两表,从后往前插入两个表中最大的元素
int combineMax(SqList *La,SqList*Lb){
    int curLength = 0; //表示新插入元素的个数
    int i = La->length-1,j =0;
    while (i>=0&& j<Lb->length)
    {
        if(La->pList[i] > Lb->pList[j]){
                La->pList[La->listSize-1-curLength] = La->pList[i]; 
                i--;
        }else{
            La->pList[La->listSize-1-curLength] = Lb->pList[j];
            j++;
        }
        curLength++;
    }

    while (j<Lb->length)
    {
        La->pList[La->listSize-1-curLength] = Lb->pList[j];
        j++;
        curLength++;
    }
    //如果A表有剩余不用管，原本就在这个地方不需要移动
    La->length +=Lb->length;
    return 1; 
}
//插入排序（部分）
int insertSort(SqList *L,int r){
    int i,j;
    for ( i = r; i <L->length; i++)
    {
       int temp = L->pList[i];
       for ( j = i-1; j >=0; j--)
       {
            if(L->pList[j] <= temp){
                break;
            }
            L->pList[j+1] = L->pList[j];
       }
       L->pList[j+1] = temp;
    }
    return 1;
}
//求交集 过滤法,A,B都是升序表
int insetSect(SqList *La,SqList* Lb){
    int curLength = 0;
    int i=0,j =0;
    while (i<La->length  && j<Lb->length)
    {
       if(La->pList[i] > Lb->pList[j]){
            j++;
       }else if (La->pList[i] < Lb->pList[j])
       {
            i++;
       }else{
            La->pList[curLength++] = La->pList[i];
            i++;
            j++;
       }
       
    }
    //如果有剩下的必然不属于交集
    La->length = curLength;
    return 1;
}

void except(SqList *La,SqList*Lb,SqList*Lc){
    int curLength = 0;
    int i=0,j =0;
    while (i<La->length  && j<Lb->length)
    {
       if(La->pList[i] > Lb->pList[j]){
            Lc->pList[curLength++] = Lb->pList[j];
            j++;
       }else if (La->pList[i] < Lb->pList[j])
       {    Lc->pList[curLength++] = La->pList[i];
            i++;
       }else{
           
            i++;
            j++;
       }
       
    }
    while (j<Lb->length)
    {
        Lc->pList[curLength++] = Lb->pList[j];
        j++; 
    }
     while (i<La->length)
    {
        Lc->pList[curLength++] = La->pList[i];
        i++; 
    }
    Lc->length = curLength;
}
//使得顺序表L逆置
int reverse(SqList * L){
    int low = 0,high = L->length-1;
    while (low < high)
    {
       int temp = L->pList[low];
       L->pList[low] = L->pList[high];
       L->pList[high] =temp;
       low ++;
       high--;
    }
    
}
//将顺序表左循环r
int reverse02(SqList* L,int startIndex ,int lastIndex){
     int low = startIndex,high = lastIndex;
    while (low < high)
    {
       int temp = L->pList[low];
       L->pList[low] = L->pList[high];
       L->pList[high] =temp;
       low ++;
       high--;
    }
}

int leftCircle(SqList* L,int r){
    reverse02(L,0,L->length-1);
    reverse02(L,0,L->length-r-1);
    reverse02(L,L->length-r,L->length-1);

}
int main(){
        SqList La,Lb,Lc;
        initSqlist(&La);
        initSqlist(&Lb);
        initSqlist(&Lc);
        int a[6] = {0,3,4,5,6};
        int b[6] = {2,5,6,8,9};
        La.length = 5;
        La.pList = a;
        Lb.length = 5;
        Lb.pList = b;

        print(&La);
        leftCircle(&La,3);
        print(&La);
}

